PaperlayerView exact revision on arXiv

Source-linked AI summary

Construction of FuzzyFind Dictionary using Golay Coding Transformation for Searching Applications

Kamran Kowsari, Maryam Yammahi, Nima Bari, Roman Vichr, Faisal Alsaby, Simon Y. Berkovich

arXiv:1503.06483v1cs.DBcs.AIcs.DScs.IRcs.LG

TL;DR

Searching large data volumes is presented as challenging, and the paper proposes constructing a FuzzyFind Dictionary through Golay-code hash transformations. The dictionary represents letters as binary vectors and targets retrieval within Hamming distance 2; the reported construction has 16 addresses in 98.83% of entries.

  • Problem

    The paper frames fast fuzzy searching over big data as difficult, noting that conventional clustering does not cover fuzzy logic and that prior encrypted-cloud fuzzy search time depended on keyword length and edit distance.

    Source: §I · p. 1, §II · p. 2

  • Method

    The method maps letter presence to 23-bit vectors and uses Golay-code clustering and transformation hash tables to build a FuzzyFind Dictionary.

    Source: §III · p. 2, D. FuzzyFind Dictionary · p. 4, §V · p. 5

  • Results

    98.83% of the FuzzyFind Dictionary has 16 addresses, while less than 1.16% has one address.

    Source: §V · p. 5

  • Takeaways & Limitations

    The dictionary represents word distortions as nearby binary vectors and is described as supporting matching within Hamming distance 2.

    Source: §V · p. 5

    The described Golay-code indexing uses 23-bit vectors, and attributes must be mapped so that closeness corresponds to Hamming closeness.

    Source: §V · p. 5

Abstract

from arXiv · show

Searching through a large volume of data is very critical for companies, scientists, and searching engines applications due to time complexity and memory complexity. In this paper, a new technique of generating FuzzyFind Dictionary for text mining was introduced. We simply mapped the 23 bits of the English alphabet into a FuzzyFind Dictionary or more than 23 bits by using more FuzzyFind Dictionary, and reflecting the presence or absence of particular letters. This representation preserves closeness of word distortions in terms of closeness of the created binary vectors within Hamming distance of 2 deviations. This paper talks about the Golay Coding Transformation Hash Table and how it can be used on a FuzzyFind Dictionary as a new technology for using in searching through big data. This method is introduced by linear time complexity for generating the dictionary and constant time complexity to access the data and update by new data sets, also updating for new data sets is linear time depends on new data points. This technique is based on searching only for letters of English that each segment has 23 bits, and also we have more than 23-bit and also it could work with more segments as reference table.

I. INTRODUCTION

The paper targets fuzzy searching over big data, where conventional clustering is described as unable to cover fuzzy logic. It proposes using Golay-code clustering and transformation tables to generate a FuzzyFind Dictionary.

I. INTRODUCTION

  • The authors state that conventional clustering cannot cover fuzzy logic.Source: §I · p. 1
  • The paper aims to generate a FuzzyFind Dictionary for searching big data by modifying GCCHT use, generating GCTHT, and then creating the dictionary.The authors cite an average of around 80 ms for one Fuzzy C-means data set as a reason they consider that method unsuitable for big data.Source: §I · p. 1

II. RELATED WORK

The related work describes limits in prior fuzzy-search approaches and in traditional uses of GCTHT. The paper draws on Golay coding, including its 23-bit form and use of overlapping hash values for error correction.

II. RELATED WORK

  • Prior fuzzy keyword search on encrypted cloud storage is described as having search time dependent on keyword length and edit distance [13].Source: §II · p. 1
  • The paper describes the 23-bit Golay code as the linear-time form and its transformation with two hashes and overlapping hash values as supporting error correction [14, 18].Source: §II · p. 2
  • Traditional GCTHT use for clustering made fuzzy logic unavailable and feature order affected output, requiring another algorithm or manual reordering [1] [2].Source: §II · p. 2

III. METHODOLOGY

The methodology builds on GCCHT to generate GCTHT, then constructs a FuzzyFind Dictionary with more addresses in most entries. The figures depict this generation pipeline and a general view of the dictionary.

III. METHODOLOGY

  • The FuzzyFind Dictionary has 16 23-bit addresses in more than 98% of its hash table, while fewer than 2% have one address.The text contrasts this with GCTHT, where 86.47% of entries have 15 23-bit values and 13.53% have one.Source: §III · p. 2
  • GCCHT has 2^23 indices, with 86.47% holding six 12-bit labels and the remainder holding one.Source: §III · p. 2
  • GCTHT has the same data structure as GCCHT, and the authors describe its one-value entries as making it inefficient for searching.Source: §III · p. 2
  • GCCHT is the starting structure; it generates GCTHT, which is then used to create the FuzzyFind Dictionary.Figure 1 presents the process as preprocessing for text mining and big-data searching.Source: Figure 1 · p. 2, §III · p. 2
  • Figure 2 is presented as a general view of the FuzzyFind Dictionary and its improved fuzziness logic from GCTHT [4, 7].Source: Figure 2 · p. 3

A. Golay Code Transformation Hash Table

GCTHT is constructed from GCCHT by combining labels across a 2^23-index hash table. The described structure contains 15 address items, with most indices associated with six labels.

A. Golay Code Transformation Hash Table

B. Fuzzy Searching

The section presents fuzzy searching through a FuzzyFind Dictionary and describes Golay-based hash transformations. It outlines how the engine connects input and output spaces.

B. Fuzzy Searching

  • Golay Code Transformation Hash Table generation pairs shifted 12-bit hashes, combines them with OR, then applies a right shift and XOR.The stated procedure loops over pairs of hashes from the index.Source: B. Fuzzy Searching · p. 3
  • Figure 3 presents the FuzzyFind Dictionary data structure using a hash table.Source: Figure 3 · p. 3
  • The described transformation iterates over 223 indices and 24 variants, decodes each 23-bit codeword, and stores resulting hash values.The procedure also saves a zero index and organizes hashes by six indices when they contain two different values.Source: B. Fuzzy Searching · p. 3
  • Figure 4 depicts how the Fuzzy Search Engine works with input and output spaces.Source: Figure 4 · p. 4

C. FuzzyFind Data Structure

The FuzzyFind Dictionary is described as a hash-based structure with 2^23 indices, typically storing 16 addresses per index.

C. FuzzyFind Data Structure

D. FuzzyFind Dictionary

The dictionary uses Golay-derived hashes and Hamming-distance neighborhoods to associate nearby 23-bit indices with shared mappings. Its construction handles cases with differing numbers of available mappings.

D. FuzzyFind Dictionary

  • In Case A, 86.47% of inputs yield six 12-bit Golay hashes that are transformed into 15 pairs; Case B yields one hash for 13.53%.Source: D. FuzzyFind Dictionary · p. 4
  • When an index lacks 15 mapped addresses, the construction checks XOR offsets 1, 2, and 4 before creating a one-address fallback.Source: D. FuzzyFind Dictionary · p. 4
  • Indices at Hamming distance at most 2 are reported to have at least one shared mapping index.Source: Figure 5 · p. 4

IV. RESULTS

The testing procedure checks whether indices within Hamming distance 2 share an address with a selected index. Figure 6 categorizes indices by their availability of 15 addresses.

IV. RESULTS

  • The test checks 277 indices per selected 23-bit index: one at distance 0, 23 at distance 1, and 253 at distance 2.Source: §IV · p. 4
  • The dictionary is considered working only if all 277 tested indices share an address with the selected index.Source: §IV · p. 5
  • Figure 6 distinguishes indices with 15 addresses already in GCTHT, those where the algorithm finds 15, and those left with one address.Its second chart reports each case as a percentage; the supplied passage does not give the plotted values.Source: Figure 6 · p. 5

V. DISCUSSION

The FuzzyFind Dictionary maps English letters into 23-bit vectors and aims to preserve word-distortion closeness within Hamming distance 2. The discussion reports 98.83% 16-address coverage and presents Figure 7 as addressing use beyond 23 bits.

V. DISCUSSION

  • 98.83% of FuzzyFind Dictionary indices have 16 addresses, while less than 1.16% have one address.Case A accounts for about 86.47% and Case B about 12.35% of indices with 16 addresses.Source: §V · p. 5
  • The dictionary maps the 26 English letters into 23 bits, with letter presence or absence represented in binary vectors.The paper says this representation keeps word distortions close in vector space within Hamming distance 2.Source: §V · p. 5
  • The retrieval scheme requires attributes to map to nearby binary vectors, limits Golay-code vectors to 23 bits, and typically allows Hamming distance 2.These constraints qualify the closeness preserved by the representation.Source: §V · p. 5
  • Figure 7 concerns using the FuzzyFind Dictionary for more than 23 bits.Source: Figure 7 · p. 5

VI. CONCLUSION AND FUTURE WORK

The conclusion presents the FuzzyFind Dictionary as a Golay-transformation-based structure for fuzzy search. It reports high 16-address coverage and linear construction, with constant-time access, while identifying search, error-correction, and future data-analysis uses.

VI. CONCLUSION AND FUTURE WORK

  • 98.83% of FuzzyFind Dictionary indices have sixteen addresses, compared with 86.47% for GCTHT.The conclusion describes the dictionary as improving the share of indices with sixteen addresses.Source: §VI · p. 6
  • The method generates GCTHT and GCAT in linear time, then applies the FuzzyFind Dictionary algorithm to generate the dictionary in linear time.It describes three construction cases: six unique 12-bit indices, one 12-bit index with multiple nearby addresses, and a one-address case.Source: §VI · p. 6
  • Hash-table organization gives constant-time access to the FuzzyFind Dictionary, while incorporating new data sets is described as linear in the new data points.Source: §VI · p. 6
  • The authors identify search engines and correction of misspellings, communication interruptions, missing landmarks, and null or unusual fields as possible uses.Source: §VI · p. 6
  • Future plans include supervised-learning indexing with historical data and applying fuzzy logic to DNA and RNA analysis, including possible tumor diagnosis.The paper also mentions gene-sequence mining as a potential application.Source: §VI · p. 6

IX. AUTHOR’S PROFILE

The author profiles describe contributors’ education, roles, experience, and research interests across computer science, data mining, machine learning, clustering, and information retrieval.

IX. AUTHOR’S PROFILE

  • Kamran Kowsari is a George Washington University computer science Ph.D. candidate with software, systems, and database engineering experience and interests including machine learning and algorithms.Source: §IX · p. 7
  • Maryam Yammahi’s profile identifies a computer science Ph.D. and interests in data mining, machine learning, fuzzy searching, and mathematical models.Source: §IX · p. 7
  • Nima Bari’s profile identifies a computer science Ph.D. and interests in data mining, machine learning, fuzzy clustering, and knowledge discovery.Source: §IX · p. 7
  • Faisal Alsaby is a George Washington University computer science Ph.D. candidate whose research interests include big-data clustering and machine learning.Source: §IX · p. 7
  • Simon Y. Berkovich is a professor at George Washington University whose areas include information retrieval, computer organization, and mathematical modeling.Source: §IX · p. 7
Loading 1503.06483v1…