A maximum dimension partitioning approach for efficiently finding all similar pairs

Jia Ling Koh*, Shao Chun Peng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

For solving the All Pair Similarity Search (APSS) problem efficiently, this paper provides a maximum dimension partitioning approach to effectively filter non-similar pairs in an early stage. At first, for each data point, the dimension with the maximum value is used to decide the corresponding segment of data partition. An adjusting method is designed to balance the number of elements in each data segment. The similar pairs consist of inter-segment similar pairs and intra-segment similar pairs, where most effort of computing APSS comes from the computation of finding inter-segment similar pairs. For speeding up the computation, a pilot-vector is used to represent each segment for estimating the upper bound of similarity between each segment pair. Only the segment pairs, whose upper bounds of similarity are larger than the given similarity threshold, need to generate the inter-segment data pairs as candidates. Moreover, based on the proposed partitioning method, we designed a MapReduce framework to solve the APSS problem in parallel. The performance evaluation results show the proposed method provides better pruning effectiveness on non-similar data pairs than the related works. Moreover, the proposed partition-based method can properly fit into the MapReduce programming scheme to effectively reduce the response time of solving the APSS problem.

Original languageEnglish
Title of host publicationBig Data Analytics and Knowledge Discovery - 18th International Conference, DaWaK 2016, Proceedings
EditorsSanjay Madria, Takahiro Hara
PublisherSpringer Verlag
Pages163-178
Number of pages16
ISBN (Print)9783319439457
DOIs
Publication statusPublished - 2016
Event18th International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2016 - Porto, Portugal
Duration: 2016 Sept 62016 Sept 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9829 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2016
Country/TerritoryPortugal
CityPorto
Period2016/09/062016/09/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'A maximum dimension partitioning approach for efficiently finding all similar pairs'. Together they form a unique fingerprint.

Cite this