Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 LIU1,2, Wenjian LUO1,2(), Lihua YUE1,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