Skip to Content
GAČR 15-08916S
Efficient subgraph discovery for petabyte-scale web analysis
2015 - 2017

The study of network behaviors without packet content inspection is becoming of increasing concern in context of network administration and security. Recent years observe an increasing demand for machine learning algorithms on graphs, since modeling interactions between entities by graphs is natural in context of large computer networks. A promising approach to modeling graphs that leverages the advantages of machine learning techniques is based on the so-called ``graphlets'', that provide embedding of graph fragments into vector spaces. However, wider adoption of graphlets is hindered by the cost of embedding and limitation to unweighted undirected graphs. In this project, we would like to focus on the design of generalized graphlet-based models and the respective vocabularies, and thus to increase the variety of applications potentially benefiting from graphlet-based descriptors. The proposed methodology will be verified within the domain of network security. In particular, malicious web communities will be searched on petabyte-scale network traffic database available to Cisco.

Principal investigator : Jakub Lokoc
Team member : Tomas Skopal, Premek Cech
GAUK 910913
Real-time Exploration Queries in Multimedia Databases
2013 - 2015

Nowadays, the similarity search in multimedia databases is performed through similarity queries explicitly specified by users. The queries return a certain part of the database that is relevant to the user specified query parameters. However, this approach suffers in case the user does not know how to specify the query, or actually she/he only wants to know what the database contains in the whole picture. In such case non-standard access to data is more appropriate, e.g., the exploration of a multimedia database.
During the exploration process the user gains a complex idea of all the stored data rather than a particular part of database returned as the result of some similarity query. In the complex view the user is osupported in browsing the space of multimedia data (typically by multi-touch device, provided by modern technologies, e.g., iPad) and that results in stream of similarity queries. For a convenient user-friendly browsing, the exploration system has to evaluate these queries promptly, which is not guaranteed in case of standard query processing (even approximate). Hence, the goal of this project is to propose and implement access methods that provide functionality of real-time similarity retrieval, thus founding fundamentals for user-friendly exploration of multimedia databases.

Principal investigator : Juraj Mosko
Team member : Tomas Skopal, Tomas Bartos, Jakub Lokoc, Tomas Grosup
CISCO 2013
Finding similar events within IDS
2013 - 2014
Principal investigator : Tomas Skopal
Team member : Jakub Lokoc, Juraj Mosko
GAČR P202/12/P297
Synergistic Modeling of Adaptive Similarities for Multimedia Retrieval
2012 - 2014

The task of smart similarity search in huge multimedia databases remains still a big challenge for the image retrieval research. The domain experts try to design more effective retrieval models which often utilize complex and expensive similarity measures. At the same time, the database experts developing similarity-based indexes have to fight with less "indexable" similarity spaces induced by the more complex similarity measures. Moreover, since there is a common practice that the provided similarity measures are considered as black-box algorithms, only general ap-proaches enabling efficiency tuning can be employed (e.g., the TriGen algorithm). However, the general approaches are not sufficient and so the database experts can no longer stand aside from the similarity modeling. In this project, we would like to "open the Pandora's box" and enter the world of domain experts, in order to design "indexable" similarity spaces. In general, we would like to describe a new similarity space modeling schema considering not only the retrieval quality but also the efficiency issues. In other words, we plan to introduce indexability measures to the similarity modeling process and investigate more variants of popular multimedia distance spaces. As we have recently shown [Beecks et al. 2011] in cooperation with RWTH Aachen, this ap-proach can result in interesting tradeoffs, where at least two orders of magnitude speedup can be achieved for the price of only slightly decreased retrieval quality.

Principal investigator : Jakub Lokoc
GAČR P202/11/0968
Large-scale Nonmetric Similarity Search in Complex Domains
2011 - 2014

The similarity search is popular in various areas of computing, including multimedia databases, data mining, bioinformatics, etc. For a long time, the database approaches to similarity search assumed the similarity as a metric distance. Due to its properties, metric similarity allows to index a database such that it can be queried efficiently (quickly). However, together with the increasing complexity of data across various domains, there appeared many similarities in recent years that were not metrics (i.e., nonmetrics). The database research, however, is still not aware of the huge potential market for nonmetric similarity search, recognizing just the metric space model.

            This project aims to propose formal models followed by a design of access methods for efficient nonmetric similarity search, that is, search in databases where the similarity is not restricted by the metric postulates. Such a goal would bring an efficient database solution to the domain experts that need to pursue large-scale content-based retrieval tasks in complex databases, like multimedia retrieval, similarity-based data mining, complex pattern matching, classification and prediction in bioinformatics, etc.

Principal investigator : Tomas Skopal
Team member : David Hoksza, Jakub Lokoc, Jiri Novak, Juraj Mosko, Tomas Bartos
GAUK 430711
Application of Metric and Non-metric Indexing Methods in Computational Proteomics
2011 - 2012

The volume of unstructured databases grows extremely whereas its annotation is problematic. The similarity search concept based on a similarity function defined for each pair of database objects is more suitable for this kind of data. The similarity is usually modelled by a distance function satisfying metric axioms, which allows efficient indexing. However, metric axioms can be very restrictive for domain experts who may prefer non-metric functions. Hence database experts have to solve this problem by converting non-metric functions to metric ones or by developing new types of non-metric indexing methods.

One of the areas where metric/non-metric similarity searching is used is computational proteomics. During the determination of the biological function of an "unknown" protein, retrieval of "known" proteins with similar structures (and thus probably with similar function) is very useful. Moreover, fast and cheap determination of protein structures is also an open problem. From database point of view, it is possible to use databases of known protein structures to address this problem. In this approach, sequence-structure similarity functions are used to obtain structures that can be similar to the searched structure of the protein.

Our goal is developing high-quality structure and sequence-structure similarity functions and methods for their indexing.

Principal investigator : Jakub Galgonek
Team member : Tomas Skopal, Jiri Novak, Jakub Lokoc
GAUK 18208
Distributed and parallel metric indexing in multimedia databases
2008 - 2009

Current data processing applications use data with considerably less structure and much less precise queries than traditional database systems. The multimedia data, like images or videos, that offer query-by-example search, are a typical example. Such data can neither be ordered in a canonical manner nor meaningfully searched by precise database queries that would return exact matches. This novel situation is what has given rise to a similarity searching. The most general approach to the similarity search, still allowing construction of index structures, is modeled in metric space. Here an important issue is the efficiency - we need to achieve fast query response over huge volumes of data. During last two decades there have been developed many metric access methods and indexing structures, however, they mostly cannot scale up with the exponential growth of multimedia data volumes we encounter during last years. A way to compete this enormous growth is to design parallel and distributed solutions, either as an extension of the traditional centralized indexing techniques, or completely new ones, where the parallelism/distribution are inherent indexing properties. Hence, the goal of the proposed project is the design and implementation of parallel and distributed indexing techniques and comparison with existing centralized solutions.

Principal investigator : Jakub Lokoc
Team member : Tomas Skopal