A Skipping SvS Intersection Algorithm

Author

Chatchaval, Jaratdech ; Boonjing, Veera ; Chanvarasuth, Pisit

Author_Institution

Math. & Comput. Sci. Dept., King Mongkut´´s Inst. of Technol. Ladkrabang, Ladkrabang, Thailand

fYear

2009

fDate

2-4 April 2009

Firstpage

93

Lastpage

96

Abstract

In this paper, we propose to improve the SvS algorithm by skipping elements of the smaller set for reducing a search boundary. The boundary of skipped element is determined by boundaries of elements prior to and next to it. We perform experiments on uniformly distributed random datasets to compare our algorithm with the standard SvS. We use regression analysis to get an equation for determining an appropriate skipping number. Our results show that the skipping SvS algorithm using the equation obtained can reduce approximately 41% on the number of comparisons of the standard SvS algorithm.

Keywords

document handling; regression analysis; regression analysis; search boundary; skipped element; skipping SvS intersection algorithm; uniformly distributed random datasets; Computer science; Conference management; Engineering management; Equations; Laboratories; Mathematics; Software algorithms; Software systems; Systems engineering and theory; Technology management; Algorithm; Information Retrieval; Intersection; SvS;

fLanguage

English

Publisher

ieee

Conference_Titel

Computing, Engineering and Information, 2009. ICC '09. International Conference on

Conference_Location

Fullerton, CA

Print_ISBN

978-0-7695-3538-8

Type

conf

DOI

10.1109/ICC.2009.42

Filename

5328880