Classifying and clustering in negative databases

doi:10.1007/s11704-013-2318-9

Front Comput Sci

2013, Vol. 7

Issue (6) : 864-874 https://doi.org/10.1007/s11704-013-2318-9

RESEARCH ARTICLE

Classifying and clustering in negative databases

Ran LIU^1,2, Wenjian LUO^1,2(

), Lihua YUE^1,2

1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China; 2. Anhui Province Key Laboratory of Software Engineering in Computing and Communication, University of Science and Technology of China, Hefei 230027, China

Download: PDF(986 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Recently, negative databases (NDBs) are proposed for privacy protection. Similar to the traditional databases, some basic operations could be conducted over the NDBs, such as select, intersection, update, delete and so on. However, both classifying and clustering in negative databases have not yet been studied. Therefore, two algorithms, i.e., a k nearest neighbor (kNN) classification algorithm and a k-means clustering algorithm in NDBs, are proposed in this paper, respectively. The core of these two algorithms is a novel method for estimating the Hamming distance between a binary string and an NDB. Experimental results demonstrate that classifying and clustering in NDBs are promising.

Keywords negative databases classification clustering k nearest neighbor k-means hamming distance

Corresponding Author(s): LUO Wenjian,Email:wjluo@ustc.edu.cn

Issue Date: 01 December 2013

Cite this article:

Ran LIU,Wenjian LUO,Lihua YUE. Classifying and clustering in negative databases[J]. Front Comput Sci, 2013, 7(6): 864-874.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-2318-9
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I6/864

1	Esponda F. Everything that is not important: negative databases [research frontier]. IEEE Computational Intelligence Magazine , 2008, 3(2): 60-63 doi: 10.1109/MCI.2008.919079
2	Esponda F, Forrest S, Helman P. Enhancing privacy through negative representations of data. Technical Report, DTIC Document . 2004
3	Esponda F, Forrest S, Helman P. Negative representations of information. International Journal of Information Security , 2009, 8(5): 331-345 doi: 10.1007/s10207-009-0078-1
4	Esponda F, Ackley E S, Helman P, Jia H, Forrest S. Protecting data privacy through hard-to-reverse negative databases. International Journal of Information Security , 2007, 6(6): 403-415 doi: 10.1007/s10207-007-0030-1
5	Liu R, Luo W, Wang X. A hybrid of the prefix algorithm and the q-hidden algorithm for generating single negative databases. In: Proceedings of 2011 IEEE Symposium on Computational Intelligence in Cyber Security (CICS) . 2011, 31-38 doi: 10.1109/CICYBS.2011.5949400
6	Jia H,Moore C, Strain D. Generating hard satisfiable formulas by hiding solutions deceptively. Journal of Artificial Intelligence Research , 2007, 28(1): 107-118
7	Jia H, Moore C, Strain D. Generating hard satisfiable formulas by hiding solutions deceptively. In: Proceedings of the National Conference on Artificial Intelligence . 2005, 384
8	Esponda F. Negative surveys. arXiv preprint math .ST/0608176. 2006
9	Bao Y, Luo W, Zhang X. Estimating positive surveys from negative surveys. Statistics & Probability Letters , 2013, 83(2): 551-558 doi: 10.1016/j.spl.2012.10.032
10	Xie H, Kulik L, Tanin E. Privacy-aware collection of aggregate spatial data. Data & Knowledge Engineering , 2011, 70(6): 576-595 doi: 10.1016/j.datak.2011.03.007
11	Horey J, Groat M M, Forrest S, Esponda F. Anonymous data collection in sensor networks. In: Proceedings of the 4th Annual International Conference on Mobile and Ubiquitous Systems: Networking & Services . 2007, 1-8
12	Dasgupta D, Saha S. Password security through negative filtering. In: Proceedings of 2010 International Conference on Emerging Security Technologies (EST) . 2010, 83-89 doi: 10.1109/EST.2010.37
13	Dasgupta D, Saha S. A biologically inspired password authentication system. In: Proceedings of the 5th Annual Workshop on Cyber Security and Information Intelligence Research: Cyber Security and Information Intelligence Challenges and Strategies . 2009, 41
14	Dasgupta D, Azeem R. An investigation of negative authentication systems. In: Proceedings of the 3rd International Conference on Information Warfare and Security . 2008, 117-126
15	Bringer J, Chabanne H. Negative databases for biometric data. In: Proceedings of the 12th ACMWorkshop on Multimedia and Security . 2010, 55-62
16	Esponda F, Trias E D, Ackley E S, Forrest S. A relational algebra for negative databases. University of New Mexico Technical Report , 2007
17	Esponda F, Ackley E S, Forrest S, Helman P. Online negative databases. International Journal of Unconventional Computing , 1993, 1(3): 201-220
18	Esponda F, Ackley E S, Forrest S, Helman P. Online negative databases. In: Proceedings of the 3rd International Conference on Artificial Immune Systems . 2004, 175-188 doi: 10.1007/978-3-540-30220-9_14
19	Selman B, Kautz H, Cohen B. Local search strategies for satisfiability testing. Cliques, Coloring, and Satisfiability: Second DIMACS implementation challenge , 1993, 26: 521-532
20	Fu Z, Marhajan Y, Malik S. Zchaffsat solver. Technical Report. Department of Electrical Engineering, Princeton University . 2004
21	Huang Z. Extensions to the k-means algorithm for clustering large data sets with categorical values. Data Mining and Knowledge Discovery , 1998, 2(3): 283-304 doi: 10.1023/A:1009769707641

[1]	Yunyun WANG, Jiao HAN, Yating SHEN, Hui XUE. Pointwise manifold regularization for semi-supervised learning[J]. Front. Comput. Sci., 2021, 15(1): 151303-.
[2]	Panthadeep BHATTACHARJEE, Pinaki MITRA. A survey of density based clustering algorithms[J]. Front. Comput. Sci., 2021, 15(1): 151308-.
[3]	Qianchen YU, Zhiwen YU, Zhu WANG, Xiaofeng WANG, Yongzhi WANG. Estimating posterior inference quality of the relational infinite latent feature model for overlapping community detection[J]. Front. Comput. Sci., 2020, 14(6): 146323-.
[4]	Zhihan JIANG, Yan LIU, Xiaoliang FAN, Cheng WANG, Jonathan LI, Longbiao CHEN. Understanding urban structures and crowd dynamics leveraging large-scale vehicle mobility data[J]. Front. Comput. Sci., 2020, 14(5): 145310-.
[5]	Parnika PARANJAPE, Meera DHABU, Parag DESHPANDE. A novel classifier for multivariate instance using graph class signatures[J]. Front. Comput. Sci., 2020, 14(4): 144307-.
[6]	Muhammad Aminur RAHAMAN, Mahmood JASIM, Md. Haider ALI, Md. HASANUZZAMAN. Bangla language modeling algorithm for automatic recognition of hand-sign-spelled Bangla sign language[J]. Front. Comput. Sci., 2020, 14(3): 143302-.
[7]	Xibin DONG, Zhiwen YU, Wenming CAO, Yifan SHI, Qianli MA. A survey on ensemble learning[J]. Front. Comput. Sci., 2020, 14(2): 241-258.
[8]	Hui XUE, Haiming XU, Xiaohong CHEN, Yunyun WANG. A primal perspective for indefinite kernel SVM problem[J]. Front. Comput. Sci., 2020, 14(2): 349-363.
[9]	Hui XUE, Sen LI, Xiaohong CHEN, Yunyun WANG. A maximum margin clustering algorithm based on indefinite kernels[J]. Front. Comput. Sci., 2019, 13(4): 813-827.
[10]	Ratha PECH, Dong HAO, Hong CHENG, Tao ZHOU. Enhancing subspace clustering based on dynamic prediction[J]. Front. Comput. Sci., 2019, 13(4): 802-812.
[11]	Gaoqi HE, Qi CHEN, Dongxu JIANG, Yubo YUAN, Xingjian LU. Physical-barrier detection based collective motion analysis[J]. Front. Comput. Sci., 2019, 13(2): 426-436.
[12]	Rizwan Ahmed KHAN, Alexandre MEYER, Hubert KONIK, Saida BOUAKAZ. Saliency-based framework for facial expression recognition[J]. Front. Comput. Sci., 2019, 13(1): 183-198.
[13]	Changlong WANG, Zhiyong FENG, Xiaowang ZHANG, Xin WANG, Guozheng RAO, Daoxun FU. ComR: a combined OWL reasoner for ontology classification[J]. Front. Comput. Sci., 2019, 13(1): 139-156.
[14]	Munish SAINI, Kuljit Kaur CHAHAL. Change profile analysis of open-source software systems to understand their evolutionary behavior[J]. Front. Comput. Sci., 2018, 12(6): 1105-1124.
[15]	Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.

Viewed

Full text

Abstract

Cited

Shared

Discussed