A logarithmic time complexity algorithm for pattern searching using product‐sum property

A logarithmic time complexity algorithm for pattern searching using product‐sum property

0.00 Avg rating0 Votes
Article ID: iaor20118840
Volume: 62
Issue: 5
Start Page Number: 2162
End Page Number: 2168
Publication Date: Sep 2011
Journal: Computers and Mathematics with Applications
Authors: , ,
Keywords: heuristics, datamining
Abstract:

Product–sum property states that an ordered pair ( s n , p n ) equ1 is unique for any ordered set a 1 , a 2 , , a n equ2 where a i , n N equ3, and s n equ4 and p n equ5 are the sum and product of the elements of the set, respectively. This fact has been exploited to develop an O ( log ( M ) ) equ6 time complexity algorithm for pattern searching in a large dataset, where M equ7 is the number of records in the dataset. Two potential applications (from databases and computational biology) of this property have been demonstrated to show the effectiveness and working of the proposed algorithm. The space complexity of the algorithm rises to the quadratic order.

Reviews

Required fields are marked *. Your email address will not be published.