Abstract
In this paper, we address the problem of scalable distributed similarity searching. Our work is based on single-site metric space indexing algorithms. They provide efficient way to perform range and nearest neighbor queries on arbitrary data in general metric spaces. The metric spaces are excellent abstraction that allows comparison of very complex objects (such as audio files, DNA sequences, texts). We have exploited the SDDS (Scalable and Distributed Data Structures) paradigms and P2P (Peer to Peer) systems to form a metric space similarity searching structure in distributed environment. Our proposed method is fully scalable without any centralized part and it allows performing similarity queries on stored data.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chávez, E., Navarro, G., Baeza-Yates, R., Marroquín, J.L.: Searching in metric spaces. ACM Computing Surveys 33(3), 273–321 (2001)
Devine, R.: Design and implementation of DDH: A distributed dynamic hashing algorithm. In: Lomet, D.B. (ed.) FODO 1993. LNCS, vol. 730, pp. 101–114. Springer, Heidelberg (1993)
Dohnal, V., Gennaro, C., Savino, P., Zezula, P.: Similarity join in metric spaces. In: Sebastiani, F. (ed.) ECIR 2003. LNCS, vol. 2633, pp. 452–467. Springer, Heidelberg (2003)
Hjaltason, G.R., Samet, H.: Index-driven similarity search in metric spaces. ACM Trans. Database Syst. 28(4), 517–580 (2003)
Kröll, B., Widmayer, P.: Distributing a search tree among a growing number of processors. In: Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data / SIGMOD 1994, Minneapolis, Minnesota, pp. 265–276 (1994)
Litwin, W., Neimat, M.-A., Schneider, D.A.: LH* – A scalable, distributed data structure. TODS 21(4), 480–525 (1996)
Milojicic, D.S., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., Xu, Z.: Peer-to-peer computing. Technical Report HPL-2002-57, HP Laboratories, Palo Alto (March 2002)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Schenker, S.: A scalable content-addressable network. In: Proc. of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 161–172 (2001)
Uhlmann, J.K.: Satisfying general proximity/similarity queries with metric trees. IPL: Information Processing Letters 40, 175–179 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Batko, M. (2004). Distributed and Scalable Similarity Searching in Metric Spaces. In: Lindner, W., Mesiti, M., Türker, C., Tzitzikas, Y., Vakali, A.I. (eds) Current Trends in Database Technology - EDBT 2004 Workshops. EDBT 2004. Lecture Notes in Computer Science, vol 3268. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30192-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-30192-9_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23305-3
Online ISBN: 978-3-540-30192-9
eBook Packages: Computer ScienceComputer Science (R0)