Article

Counting Distance Permutations

Author:

Matthew SkalaAuthors Info & Claims

SISAP '08: Proceedings of the First International Workshop on Similarity Search and Applications (sisap 2008)

Pages 69 - 76

https://doi.org/10.1109/SISAP.2008.15

Published: 11 April 2008 Publication History

Publisher Site

Abstract

A distance permutation index supports fast proximity searching in a high-dimensional metric space. Given some fixed reference sites, for each point in a database the index stores a permutation naming the closest site, the second-closest, and so on. We examine how many distinct permutations can occur as a function of the number of sites and the size of the space. We give theoretical results for tree metrics and vector spaces with L_1$, L_2$, and L_8$ metrics, improving on the previous best known storage space in the vector case. We also give experimental results and commentary on the number of distance permutations that actually occur in a variety of vector, string, and document spaces.

Cited By

View all

Murakami TTakahashi KSerita SFujii YFerro A(2011)Versatile probability-based indexing for approximate similarity searchProceedings of the Fourth International Conference on SImilarity Search and APplications10.1145/1995412.1995423(51-58)Online publication date: 30-Jun-2011
https://dl.acm.org/doi/10.1145/1995412.1995423
Novak DBatko M(2009)Metric IndexProceedings of the 2009 Second International Workshop on Similarity Search and Applications10.1109/SISAP.2009.26(65-73)Online publication date: 29-Aug-2009
https://dl.acm.org/doi/10.1109/SISAP.2009.26

Index Terms

Counting Distance Permutations
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration

Recommendations

Counting distance permutations

Distance permutation indexes support fast proximity searching in high-dimensional metric spaces. Given some fixed reference sites, for each point in a database the index stores a permutation naming the closest site, the second-closest, and so on. We ...
Bounding prefix transposition distance for strings and permutations

A transposition is an operation that exchanges two adjacent substrings. Transpositions over permutations, the sequences with no repeated symbols, are related to genome rearrangements. If one of the substrings is restricted to a prefix then it is called ...
Bounding Prefix Transposition Distance for Strings and Permutations
HICSS '08: Proceedings of the Proceedings of the 41st Annual Hawaii International Conference on System Sciences

A transposition is an operation that exchanges two adjacent substrings. When it is restricted so that one of the substrings is a prefix, it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SISAP '08: Proceedings of the First International Workshop on Similarity Search and Applications (sisap 2008)

April 2008

143 pages

ISBN:9780769531014

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Murakami TTakahashi KSerita SFujii YFerro A(2011)Versatile probability-based indexing for approximate similarity searchProceedings of the Fourth International Conference on SImilarity Search and APplications10.1145/1995412.1995423(51-58)Online publication date: 30-Jun-2011
https://dl.acm.org/doi/10.1145/1995412.1995423
Novak DBatko M(2009)Metric IndexProceedings of the 2009 Second International Workshop on Similarity Search and Applications10.1109/SISAP.2009.26(65-73)Online publication date: 29-Aug-2009
https://dl.acm.org/doi/10.1109/SISAP.2009.26

Abstract

Cited By

Index Terms

Recommendations