Efficient Similarity Search with Constant Scalability
Project goals
Mainly due to the boom of digital recording devices, there is more and more digital data being produced nowadays. This trend of increase is observable in two respects - growing data volumes, and also the variety of data types. Because this new data oftenrequires new approaches to processing and searching, a considerable effort has been put in the area of similarity search. However, a general, efficient and, especially, scalable solution of this issue is still a resisting research challenge. The purposeand goal of this project is to propose universal and efficient data structures for similarity search that would have, ideally, constant search costs with respect to growing data volume. The research will be based upon our experience in this area and will follow two directions: 1) recursive partitioning of metric space using a fixed set of pivots and 2) a combination of several orthogonal indexes. Suggested approaches will be implemented, tested on real data, and used to build several search systems, among others, on a database consisting of hundreds of millions digital images.
Keywords
similaritysearchmultimediadatastructurespeer-to-peernetworkscalability
Public support
Provider
Czech Science Foundation
Programme
Post-graduate (doctorate) grants
Call for proposals
Postdoktorandské granty 10 (SGA02010GA1PD)
Main participants
—
Contest type
VS - Public tender
Contract ID
P202-10-P220
Alternative language
Project name in Czech
Podobnostní vyhledávání s konstantní škálovatelností
Annotation in Czech
Díky rozmachu digitálních záznamových zařízení produkuje lidstvo stále více elektronických dat. Tento nárůst se netýká pouze samotného objemu dat, ale také rozmanitosti datových typů. Protože nová data často vyžadují nové postupy zpracování a vyhledávánív nich, je věnováno nemalé úsilí oblasti tzv. podobnostního vyhledávání. Doposud ale nebyl navržen vyhledávací mechanismus, který by byl obecný, dostatečně efektivní a zejména škálovatelný - tedy použitelný pro velké objemy dat. Cílem projektu je nalezení univerzálních a efektivních datových struktur pro podobnostní vyhledávání, které by měly, ideálně, konstantní vyhledávací náklady vzhledem k rostoucímu objemu zpracovávaných dat. Výzkum bude vycházet z našich zkušeností v této oblasti a bude sledovattyto dvě linie: 1) rekurzivní dělení metrického prostoru pomocí fixní množiny pivotů a 2) kombinace několika ortogonálních indexů. Navržené vyhledávací techniky budou implementovány, testovány na reálných datech a použity pro vytvoření několika vyhledávacích systémů, mj. na databázi mající stovky milionů digitálních obrázků.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The goals of this project were fulfilled. The results were published in international journals and proceedings of international conferences. The number of publications is somewhat smaller than the number planned in the project application. All publications have a number of coauthors and were supported by multiple grants of the Czech Science Foundation.
Solution timeline
Realization period - beginning
Jan 1, 2010
Realization period - end
Dec 31, 2012
Project status
U - Finished project
Latest support payment
Apr 1, 2012
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP13-GA0-GP-U/03:3
Data delivery date
May 2, 2016
Finance
Total approved costs
576 thou. CZK
Public financial support
576 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
576 CZK thou.
Public support
576 CZK thou.
0%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2010 - 31. 12. 2012