Visible to the public Biblio

Found 197 results

Filters: First Letter Of Title is G  [Clear All Filters]
A B C D E F [G] H I J K L M N O P Q R S T U V W X Y Z   [Show ALL]
Wang, Xiaoyin, Qin, Xue, Bokaei Hosseini, Mitra, Slavin, Rocky, Breaux, Travis D., Niu, Jianwei.  2018.  GUILeak: Tracing Privacy Policy Claims on User Input Data for Android Applications. 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE). :37–47.
The Android mobile platform supports billions of devices across more than 190 countries around the world. This popularity coupled with user data collection by Android apps has made privacy protection a well-known challenge in the Android ecosystem. In practice, app producers provide privacy policies disclosing what information is collected and processed by the app. However, it is difficult to trace such claims to the corresponding app code to verify whether the implementation is consistent with the policy. Existing approaches for privacy policy alignment focus on information directly accessed through the Android platform (e.g., location and device ID), but are unable to handle user input, a major source of private information. In this paper, we propose a novel approach that automatically detects privacy leaks of user-entered data for a given Android app and determines whether such leakage may violate the app's privacy policy claims. For evaluation, we applied our approach to 120 popular apps from three privacy-relevant app categories: finance, health, and dating. The results show that our approach was able to detect 21 strong violations and 18 weak violations from the studied apps.
Quanyan Zhu, University of Illinois at Urbana-Champaign, Carol Fung, Raouf Boutaba, Tamer Başar, University of Illinois at Urbana-Champaign.  2012.  GUIDEX: A Game-Theoretic Incentive-Based Mechanism for Intrusion Detection Networks. IEEE Journal on Selected Areas in Communications. 30(11)

Traditional intrusion detection systems (IDSs) work in isolation and can be easily compromised by unknown threats. An intrusion detection network (IDN) is a collaborative IDS network intended to overcome this weakness by allowing IDS peers to share detection knowledge and experience, and hence improve the overall accuracy of intrusion assessment. In this work, we design an IDN system, called GUIDEX, using gametheoretic modeling and trust management for peers to collaborate truthfully and actively. We first describe the system architecture and its individual components, and then establish a gametheoretic framework for the resource management component of GUIDEX. We establish the existence and uniqueness of a Nash equilibrium under which peers can communicate in a reciprocal incentive compatible manner. Based on the duality of the problem, we develop an iterative algorithm that converges geometrically to the equilibrium. Our numerical experiments and discrete event simulation demonstrate the convergence to the Nash equilibrium and the security features of GUIDEX against free riders, dishonest insiders and DoS attacks

Ku, Yeeun, Park, Leo Hyun, Shin, Sooyeon, Kwon, Taekyoung.  2018.  A Guided Approach to Behavioral Authentication. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. :2237-2239.

User's behavioral biometrics are promising as authentication factors in particular if accuracy is sufficiently guaranteed. They can be used to augment security in combination with other authentication factors. A gesture-based pattern lock system is a good example of such multi-factor authentication, using touch dynamics in a smartphone. However, touch dynamics can be significantly affected by a shape of gestures with regard to the performance and accuracy, and our concern is that user-chosen patterns are likely far from producing such a good shape of gestures. In this poster, we raise this problem and show our experimental study conducted in this regard. We investigate if there is a reproducible correlation between shape and accuracy and if we can derive effective attribute values for user guidance, based on the gesture-based pattern lock system. In more general, we discuss a guided approach to behavioral authentication.

Chandrala, M S, Hadli, Pooja, Aishwarya, R, Jejo, Kevin C, Sunil, Y, Sure, Pallaviram.  2019.  A GUI for Wideband Spectrum Sensing using Compressive Sampling Approaches. 2019 10th International Conference on Computing, Communication and Networking Technologies (ICCCNT). :1–6.
Cognitive Radio is a prominent solution for effective spectral resource utilization. The rapidly growing device to device (D2D) communications and the next generation networks urge the cognitive radio networks to facilitate wideband spectrum sensing in order to assure newer spectral opportunities. As Nyquist sampling rates are formidable owing to complexity and cost of the ADCs, compressive sampling approaches are becoming increasingly popular. One such approach exploited in this paper is the Modulated Wideband Converter (MWC) to recover the spectral support. On the multiple measurement vector (MMV) framework provided by the MWC, threshold based Orthogonal Matching Pursuit (OMP) and Sparse Bayesian Learning (SBL) algorithms are employed for support recovery. We develop a Graphical User Interface (GUI) that assists a beginner to simulate the RF front-end of a MWC and thereby enables the user to explore support recovery as a function of Signal to Noise Ratio (SNR), number of measurement vectors and threshold. The GUI enables the user to explore spectrum sensing in DVB-T, 3G and 4G bands and recovers the support using OMP or SBL approach. The results show that the performance of SBL is better than that of OMP at a lower SNR values.
Blake, M. Brian, Helal, A., Mei, H..  2019.  Guest Editor's Introduction: Special Section on Services and Software Engineering Towards Internetware. IEEE Transactions on Services Computing. 12:4–5.
The six papers in this special section focuses on services and software computing. Services computing provides a foundation to build software systems and applications over the Internet as well as emerging hybrid networked platforms motivated by it. Due to the open, dynamic, and evolving nature of the Internet, new features were born with these Internet-scale and service-based software systems. Such systems should be situation- aware, adaptable, and able to evolve to effectively deal with rapid changes of user requirements and runtime contexts. These emerging software systems enable and require novel methods in conducting software requirement, design, deployment, operation, and maintenance beyond existing services computing technologies. New programming and lifecycle paradigms accommodating such Internet- scale and service-based software systems, referred to as Internetware, are inevitable. The goal of this special section is to present the innovative solutions and challenging technical issues, so as to explore various potential pathways towards Internet-scale and service-based software systems.
Kalyanaraman, A., Halappanavar, M..  2018.  Guest Editorial: Advances in Parallel Graph Processing: Algorithms, Architectures, and Application Frameworks. IEEE Transactions on Multi-Scale Computing Systems. 4:188—189.

The papers in this special section explore recent advancements in parallel graph processing. In the sphere of modern data science and data-driven applications, graph algorithms have achieved a pivotal place in advancing the state of scientific discovery and knowledge. Nearly three centuries of ideas have made graph theory and its applications a mature area in computational sciences. Yet, today we find ourselves at a crossroads between theory and application. Spurred by the digital revolution, data from a diverse range of high throughput channels and devices, from across internet-scale applications, are starting to mark a new era in data-driven computing and discovery. Building robust graph models and implementing scalable graph application frameworks in the context of this new era are proving to be significant challenges. Concomitant to the digital revolution, we have also experienced an explosion in computing architectures, with a broad range of multicores, manycores, heterogeneous platforms, and hardware accelerators (CPUs, GPUs) being actively developed and deployed within servers and multinode clusters. Recent advances have started to show that in more than one way, these two fields—graph theory and architectures–are capable of benefiting and in fact spurring new research directions in one another. This special section is aimed at introducing some of the new avenues of cutting-edge research happening at the intersection of graph algorithm design and their implementation on advanced parallel architectures.

Pupo, Angel Luis Scull, Nicolay, Jens, Boix, Elisa Gonzalez.  2018.  GUARDIA: Specification and Enforcement of Javascript Security Policies Without VM Modifications. Proceedings of the 15th International Conference on Managed Languages & Runtimes. :17:1–17:15.
The complex architecture of browser technologies and dynamic characteristics of JavaScript make it difficult to ensure security in client-side web applications. Browser-level security policies alone are not sufficient because it is difficult to apply them correctly and they can be bypassed. As a result, they need to be completed by application-level security policies. In this paper, we survey existing solutions for specifying and enforcing application-level security policies for client-side web applications, and distill a number of desirable features. Based on these features we developed Guardia, a framework for declaratively specifying and dynamically enforcing application-level security policies for JavaScript web applications without requiring VM modifications. We describe Guardia enforcement mechanism by means of JavaScript reflection with respect to three important security properties (transparency, tamper-proofness, and completeness). We also use Guardia to specify and deploy 12 access control policies discussed in related work in three experimental applications that are representative of real-world applications. Our experiments indicate that Guardia is correct, transparent, and tamper-proof, while only incurring a reasonable runtime overhead.
Leon, S., Perelló, J., Careglio, D., Tarzan, M..  2017.  Guaranteeing QoS requirements in long-haul RINA networks. 2017 19th International Conference on Transparent Optical Networks (ICTON). :1–4.

In the last years, networking scenarios have been evolving, hand-in-hand with new and varied applications with heterogeneous Quality of Service (QoS) requirements. These requirements must be efficiently and effectively delivered. Given its static layered structure and almost complete lack of built-in QoS support, the current TCP/IP-based Internet hinders such an evolution. In contrast, the clean-slate Recursive InterNetwork Architecture (RINA) proposes a new recursive and programmable networking model capable of evolving with the network requirements, solving in this way most, if not all, TCP/IP protocol stack limitations. Network providers can better deliver communication services across their networks by taking advantage of the RINA architecture and its support for QoS. This support allows providing complete information of the QoS needs of the supported traffic flows, and thus, fulfilment of these needs becomes possible. In this work, we focus on the importance of path selection to better ensure QoS guarantees in long-haul RINA networks. We propose and evaluate a programmable strategy for path selection based on flow QoS parameters, such as the maximum allowed latency and packet losses, comparing its performance against simple shortest-path, fastest-path and connection-oriented solutions.

Chen, J., Liao, S., Hou, J., Wang, K., Wen, J..  2020.  GST-GCN: A Geographic-Semantic-Temporal Graph Convolutional Network for Context-aware Traffic Flow Prediction on Graph Sequences. 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC). :1604–1609.
Traffic flow prediction is an important foundation for intelligent transportation systems. The traffic data are generated from a traffic network and evolved dynamically. So spatio-temporal relation exploration plays a support role on traffic data analysis. Most researches focus on spatio-temporal information fusion through a convolution operation. To the best of our knowledge, this is the first work to suggest that it is necessary to distinguish the two aspects of spatial correlations and propose the two types of spatial graphs, named as geographic graph and semantic graph. Then two novel stereo convolutions with irregular acceptive fields are proposed. The geographic-semantic-temporal contexts are dynamically jointly captured through performing the proposed convolutions on graph sequences. We propose a geographic-semantic-temporal graph convolutional network (GST-GCN) model that combines our graph convolutions and GRU units hierarchically in a unified end-to-end network. The experiment results on the Caltrans Performance Measurement System (PeMS) dataset show that our proposed model significantly outperforms other popular spatio-temporal deep learning models and suggest the effectiveness to explore geographic-semantic-temporal dependencies on deep learning models for traffic flow prediction.
Sevilla, S., Garcia-Luna-Aceves, J. J., Sadjadpour, H..  2017.  GroupSec: A new security model for the web. 2017 IEEE International Conference on Communications (ICC). :1–6.
The de facto approach to Web security today is HTTPS. While HTTPS ensures complete security for clients and servers, it also interferes with transparent content-caching at middleboxes. To address this problem and support both security and caching, we propose a new approach to Web security and privacy called GroupSec. The key innovation of GroupSec is that it replaces the traditional session-based security model with a new model based on content group membership. We introduce the GroupSec security model and show how HTTP can be easily adapted to support GroupSec without requiring changes to browsers, servers, or middleboxes. Finally, we present results of a threat analysis and performance experiments which show that GroupSec achieves notable performance benefits at the client and server while remaining as secure as HTTPS.
Lin, Han-Yu, Wu, Hong-Ru, Ting, Pei-Yih, Lee, Po-Ting.  2019.  A Group-Oriented Strong Designated Verifier Signature Scheme with Constant-Size Signatures. 2019 2nd International Conference on Communication Engineering and Technology (ICCET). :6–10.
A strong designated verifier signature (SDVS) scheme only permits an intended verifier to validate the signature by employing his/her private key. Meanwhile, for the sake of signer anonymity, the designated verifier is also able to generate a computationally indistinguishable transcript, which prevents the designated verifier from arbitrarily transferring his conviction to any third party. To extend the applications of conventional SDVS schemes, in this paper, we propose a group-oriented strong designated verifier signature (GO-SDVS) scheme from bilinear pairings. In particular, our scheme allows a group of signers to cooperatively generate a signature for a designated verifier. A significant property of our mechanism is constant-size signatures, i.e., the signature length remains constant when the number of involved signers increases. We also prove that the proposed GO-SDVS scheme is secure against adaptive chosen-message attacks in the random oracle model and fulfills the essential properties of signer ambiguity and non-transferability.
Touati, Lyes.  2017.  Grouping-Proofs Based Access Control Using KP-ABE for IoT Applications. 2017 IEEE Trustcom/BigDataSE/ICESS. :301—308.

The Internet of Things (IoT) is a new paradigm in which every-day objects are interconnected between each other and to the Internet. This paradigm is receiving much attention of the scientific community and it is applied in many fields. In some applications, it is useful to prove that a number of objects are simultaneously present in a group. For example, an individual might want to authorize NFC payment with his mobile only if k of his devices are present to ensure that he is the right person. This principle is known as Grouping-Proofs. However, existing Grouping-Proofs schemes are mostly designed for RFID systems and don't fulfill the IoT characteristics. In this paper, we propose a Threshold Grouping-Proofs for IoT applications. Our scheme uses the Key-Policy Attribute-Based Encryption (KP-ABE) protocol to encrypt a message so that it can be decrypted only if at least k objects are simultaneously present in the same location. A security analysis and performance evaluation is conducted to show the effectiveness of our proposal solution.

Daesung Choi, Sungdae Hong, Hyoung-Kee Choi.  2014.  A group-based security protocol for Machine Type Communications in LTE-Advanced. Computer Communications Workshops (INFOCOM WKSHPS), 2014 IEEE Conference on. :161-162.

We propose Authentication and Key Agreement (AKA) for Machine Type Communications (MTC) in LTE-Advanced. This protocol is based on an idea of grouping devices so that it would reduce signaling congestion in the access network and overload on the single authentication server. We verified that this protocol is designed to be secure against many attacks by using a software verification tool. Furthermore, performance evaluation suggests that this protocol is efficient with respect to authentication overhead and handover delay.

Iscen, Ahmet, Furon, Teddy.  2016.  Group Testing for Identification with Privacy. Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security. :51–56.

This paper describes an approach where group testing helps in enforcing security and privacy in identification. We detail a particular scheme based on embedding and group testing. We add a second layer of defense, group vectors, where each group vector represents a set of dataset vectors. Whereas the selected embedding poorly protects the data when used alone, the group testing approach makes it much harder to reconstruct the data when combined with the embedding. Even when curious server and user collude to disclose the secret parameters, they cannot accurately recover the data. Another byproduct of our approach is that it reduces the complexity of the search and the required storage space. We show the interest of our work in a benchmark biometrics dataset, where we verify our theoretical analysis with real data.

Emura, Keita, Hayashi, Takuya, Ishida, Ai.  2017.  Group Signatures with Time-bound Keys Revisited: A New Model and an Efficient Construction. Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. :777–788.
Chu et al. (ASIACCS 2012) proposed group signature with time-bound keys (GS-TBK) where each signing key is associated to an expiry time τ. In addition to prove the membership of the group, a signer needs to prove that the expiry time has not passed, i.e., t\textbackslashtextlessτ where t is the current time. A signer whose expiry time has passed is automatically revoked, and this revocation is called natural revocation. Simultaneously, signers can be revoked before their expiry times have passed due to the compromise of the credential. This revocation is called premature revocation. A nice property of the Chu et al. proposal is that the size of revocation lists can be reduced compared to those of Verifier-Local Revocation (VLR) group signature schemes, by assuming that natural revocation accounts for most of signer revocations in practice, and prematurely revoked signers are only a small fraction. In this paper, we point out that the definition of traceability of Chu et al. did not capture unforgeability of expiry time of signing keys which guarantees that no adversary who has a signing key associated to an expiry time τ can compute a valid signature after τ has passed. We introduce a security model that captures unforgeability, and propose a GS-TBK scheme secure in the new model. Our scheme also provides the constant signing costs whereas those of the previous schemes depend on the bit-length of the time representation. Finally, we give implementation results, and show that our scheme is feasible in practical settings.
Alshammari, H., Elleithy, K., Almgren, K., Albelwi, S..  2014.  Group signature entanglement in e-voting system. Systems, Applications and Technology Conference (LISAT), 2014 IEEE Long Island. :1-4.

In any security system, there are many security issues that are related to either the sender or the receiver of the message. Quantum computing has proven to be a plausible approach to solving many security issues such as eavesdropping, replay attack and man-in-the-middle attack. In the e-voting system, one of these issues has been solved, namely, the integrity of the data (ballot). In this paper, we propose a scheme that solves the problem of repudiation that could occur when the voter denies the value of the ballot either for cheating purposes or for a real change in the value by a third party. By using an entanglement concept between two parties randomly, the person who is going to verify the ballots will create the entangled state and keep it in a database to use it in the future for the purpose of the non-repudiation of any of these two voters.

Zhang, L., Li, C., Li, Y., Luo, Q., Zhu, R..  2017.  Group signature based privacy protection algorithm for mobile ad hoc network. 2017 IEEE International Conference on Information and Automation (ICIA). :947–952.

Nowadays, Vehicular ad hoc Network as a special class of Mobile ad hoc Network(MANET), provides plenty of services. However, it also brings the privacy protection issues, and there are conflicts between the privacy protection and the services. In this paper, we will propose a privacy protection algorithm based on group signature including two parts, group signature based anonymous verification and batch verification. The anonymous verification is based on the network model we proposed, which can reduce the trust authority burden by dividing the roadside units into different levels, and the batch verification can reduce the time of message verification in one group. We also prove our algorithm can satisfy the demand of privacy protection. Finally, the simulation shows that the algorithm we proposed is better than the BBS on the length of the signature, time delay and packet loss rate.

Palanisamy, B., Li, C., Krishnamurthy, P..  2017.  Group Privacy-Aware Disclosure of Association Graph Data. 2017 IEEE International Conference on Big Data (Big Data). :1043–1052.

In the age of Big Data, we are witnessing a huge proliferation of digital data capturing our lives and our surroundings. Data privacy is a critical barrier to data analytics and privacy-preserving data disclosure becomes a key aspect to leveraging large-scale data analytics due to serious privacy risks. Traditional privacy-preserving data publishing solutions have focused on protecting individual's private information while considering all aggregate information about individuals as safe for disclosure. This paper presents a new privacy-aware data disclosure scheme that considers group privacy requirements of individuals in bipartite association graph datasets (e.g., graphs that represent associations between entities such as customers and products bought from a pharmacy store) where even aggregate information about groups of individuals may be sensitive and need protection. We propose the notion of $ε$g-Group Differential Privacy that protects sensitive information of groups of individuals at various defined group protection levels, enabling data users to obtain the level of information entitled to them. Based on the notion of group privacy, we develop a suite of differentially private mechanisms that protect group privacy in bipartite association graphs at different group privacy levels based on specialization hierarchies. We evaluate our proposed techniques through extensive experiments on three real-world association graph datasets and our results demonstrate that the proposed techniques are effective, efficient and provide the required guarantees on group privacy.

Li, Celia, Yang, Cungang.  2018.  A Group Key Management Protocol for Mobile Devices. Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing. :300–301.

We propose a Centralized Tree based Diffie-Hellman (CTDH) protocol for wireless mesh networks, which take into account the characteristics of mesh network operations, wireless routers and mobile devices. Performance analysis shows that CTDH is more efficient than the Tree-Based Group Diffie-Hellman Protocol (TGDH).

Shukla, M. K., Dubey, A. K., Upadhyay, D., Novikov, B..  2020.  Group Key Management in Cloud for Shared Media Sanitization. 2020 Sixth International Conference on Parallel, Distributed and Grid Computing (PDGC). :117—120.
Cloud provides a low maintenance and affordable storage to various applications and users. The data owner allows the cloud users to access the documents placed in the cloud service provider based on the user's access control vector provided to the cloud users by the data owners. In such type of scenarios, the confidentiality of the documents exchanged between the cloud service provider and the users should be maintained. The existing approaches used to provide this facility are not computation and communication efficient for performing key updating in the data owner side and the key recovery in the user side. This paper discusses the key management services provided to the cloud users. Remote key management and client-side key management are two approaches used by cloud servers. This paper also aims to discuss the method for destroying the encryption/decryption group keys for shared data to securing the data after deletion. Crypto Shredding or Crypto Throw technique is deployed for the same.
Kun-Lin Tsai, Jiu-Soon Tan, Fang-Yie Leu, Yi-Li Huang.  2014.  A Group File Encryption Method using Dynamic System Environment Key. Network-Based Information Systems (NBiS), 2014 17th International Conference on. :476-483.

File encryption is an effective way for an enterprise to prevent its data from being lost. However, the data may still be deliberately or inadvertently leaked out by the insiders or customers. When the sensitive data are leaked, it often results in huge monetary damages and credit loss. In this paper, we propose a novel group file encryption/decryption method, named the Group File Encryption Method using Dynamic System Environment Key (GEMS for short), which provides users with auto crypt, authentication, authorization, and auditing security schemes by utilizing a group key and a system environment key. In the GEMS, the important parameters are hidden and stored in different devices to avoid them from being cracked easily. Besides, it can resist known-key and eavesdropping attacks to achieve a very high security level, which is practically useful in securing an enterprise's and a government's private data.

Palanisamy, B., Li, C., Krishnamurthy, P..  2017.  Group Differential Privacy-Preserving Disclosure of Multi-level Association Graphs. 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). :2587–2588.

Traditional privacy-preserving data disclosure solutions have focused on protecting the privacy of individual's information with the assumption that all aggregate (statistical) information about individuals is safe for disclosure. Such schemes fail to support group privacy where aggregate information about a group of individuals may also be sensitive and users of the published data may have different levels of access privileges entitled to them. We propose the notion ofεg-Group Differential Privacy that protects sensitive information of groups of individuals at various defined privacy levels, enabling data users to obtain the level of access entitled to them. We present a preliminary evaluation of the proposed notion of group privacy through experiments on real association graph data that demonstrate the guarantees on group privacy on the disclosed data.

Li, Qingyuan, Wu, Hao, Liu, Lei, Pan, Bin, Dong, Lan.  2018.  A Group based Dynamic Mix Zone Scheme for Location Privacy Preservation in VANETs. 2018 Third International Conference on Security of Smart Cities, Industrial Control System and Communications (SSIC). :1–5.
Modern vehicles are equipped with wireless communication technologies, allowing them to communicate with each other. Through Dedicated Short Range Communication (DSRC), vehicles periodically broadcast beacons messages for safety applications, which gives rise to disclosure of location privacy. A way to protect vehicles location privacy is to have their pseudonyms changed frequently. With restrict to limited resources (such as computation and storage), we propose a group based dynamic mix zone scheme, in which vehicles form a group when their pseudonyms are close to expire. Simulation results confirm that the proposed scheme can protect location privacy and alleviate the storage burden.
Ouaissa, Mariya, Rhattoy, A., Lahmer, M..  2017.  Group Access Authentication of Machine to Machine Communications in LTE Networks. Proceedings of the Second International Conference on Internet of Things, Data and Cloud Computing. :50:1–50:5.
Today Machine to Machine (M2M) communications are very expanded in many application areas. M2M devices are likely to be small and able to operate for long periods and transmit data through wireless links, it is also defined as machine type communication (MTC) in Release 10 of the 3GPP "3rd Generation Partnership Project". Recently, most research has focused on congestion control, sensing information and control technologies and resource management, etc, but there are not many studies on the security aspects. Indeed, M2M communications and equipments may be exposed to different types of attacks (physical attacks on equipment and recovery of sensitive data, configurations attacks to compromise the software, attacks on the communications protocol, etc). In this article we introduce security into the M2M architecture and discuss the most important question of security, which is the group access authentication by modifying existing authentication protocols, such as group authentication and key agreement protocol used to resolve the group access authentication for M2M.
Yang, C., Li, Z., Qu, W., Liu, Z., Qi, H..  2017.  Grid-Based Indexing and Search Algorithms for Large-Scale and High-Dimensional Data. 2017 14th International Symposium on Pervasive Systems, Algorithms and Networks 2017 11th International Conference on Frontier of Computer Science and Technology 2017 Third International Symposium of Creative Computing (ISPAN-FCST-ISCC). :46–51.

The rapid development of Internet has resulted in massive information overloading recently. These information is usually represented by high-dimensional feature vectors in many related applications such as recognition, classification and retrieval. These applications usually need efficient indexing and search methods for such large-scale and high-dimensional database, which typically is a challenging task. Some efforts have been made and solved this problem to some extent. However, most of them are implemented in a single machine, which is not suitable to handle large-scale database.In this paper, we present a novel data index structure and nearest neighbor search algorithm implemented on Apache Spark. We impose a grid on the database and index data by non-empty grid cells. This grid-based index structure is simple and easy to be implemented in parallel. Moreover, we propose to build a scalable KNN graph on the grids, which increase the efficiency of this index structure by a low cost in parallel implementation. Finally, experiments are conducted in both public databases and synthetic databases, showing that the proposed methods achieve overall high performance in both efficiency and accuracy.