Visible to the public Biblio

Found 631 results

Filters: First Letter Of Title is R  [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]
R
Hamamreh, Rushdi A., Ayyad, Mohammad, Jamoos, Mohammad.  2019.  RAD: Reinforcement Authentication DYMO Protocol for MANET. 2019 International Conference on Promising Electronic Technologies (ICPET). :136–141.
Mobile ad hoc network (MANET) does not have fixed infrastructure centralized server which manage the connections between the nodes. Rather, the nodes in MANET move randomly. Thus, it is risky to exchange data between nodes because there is a high possibility of having malicious node in the path. In this paper, we will describe a new authentication technique using message digest 5 (MD5), hashing for dynamic MANET on demand protocol (DYMO) based on reinforcement learning. In addition, we will describe an encryption technique that can be used without the need for a third party to distribute a secret key. After implementing the suggested model, results showed a remarkable enhancement in securing the path by increasing the packet delivery ratio and average throughput. On the other hand, there was an increase in end to end delay due to time spent in cryptographic operations.
Kadhim, Y., Mishra, A..  2019.  Radial Basis Function (RBF) Based on Multistage Autoencoders for Intrusion Detection system (IDS). 2019 1st International Informatics and Software Engineering Conference (UBMYK). :1—4.

In this paper, RBF-based multistage auto-encoders are used to detect IDS attacks. RBF has numerous applications in various actual life settings. The planned technique involves a two-part multistage auto-encoder and RBF. The multistage auto-encoder is applied to select top and sensitive features from input data. The selected features from the multistage auto-encoder is wired as input to the RBF and the RBF is trained to categorize the input data into two labels: attack or no attack. The experiment was realized using MATLAB2018 on a dataset comprising 175,341 case, each of which involves 42 features and is authenticated using 82,332 case. The developed approach here has been applied for the first time, to the knowledge of the authors, to detect IDS attacks with 98.80% accuracy when validated using UNSW-NB15 dataset. The experimental results show the proposed method presents satisfactory results when compared with those obtained in this field.

Cheng, Raymond, Scott, William, Ellenbogen, Paul, Howell, Jon, Roesner, Franziska, Krishnamurthy, Arvind, Anderson, Thomas.  2016.  Radiatus: A Shared-Nothing Server-Side Web Architecture. Proceedings of the Seventh ACM Symposium on Cloud Computing. :237–250.

Web applications are a frequent target of successful attacks. In most web frameworks, the damage is amplified by the fact that application code is responsible for security enforcement. In this paper, we design and evaluate Radiatus, a shared-nothing web framework where application-specific computation and storage on the server is contained within a sandbox with the privileges of the end-user. By strongly isolating users, user data and service availability can be protected from application vulnerabilities. To make Radiatus practical at the scale of modern web applications, we introduce a distributed capabilities system to allow fine-grained secure resource sharing across the many distributed services that compose an application. We analyze the strengths and weaknesses of a shared-nothing web architecture, which protects applications from a large class of vulnerabilities, but adds an overhead of 60.7% per server and requires an additional 31MB of memory per active user. We demonstrate that the system can scale to 20K operations per second on a 500-node AWS cluster.

Sliwa, Benjamin, Haferkamp, Marcus, Al-Askary, Manar, Dorn, Dennis, Wietfeld, Christian.  2018.  A radio-fingerprinting-based vehicle classification system for intelligent traffic control in smart cities. 2018 Annual IEEE International Systems Conference (SysCon). :1–5.
The measurement and provision of precise and up-to-date traffic-related key performance indicators is a key element and crucial factor for intelligent traffic control systems in upcoming smart cities. The street network is considered as a highly-dynamic Cyber Physical System (CPS) where measured information forms the foundation for dynamic control methods aiming to optimize the overall system state. Apart from global system parameters like traffic flow and density, specific data, such as velocity of individual vehicles as well as vehicle type information, can be leveraged for highly sophisticated traffic control methods like dynamic type-specific lane assignments. Consequently, solutions for acquiring these kinds of information are required and have to comply with strict requirements ranging from accuracy over cost-efficiency to privacy preservation. In this paper, we present a system for classifying vehicles based on their radio-fingerprint. In contrast to other approaches, the proposed system is able to provide real-time capable and precise vehicle classification as well as cost-efficient installation and maintenance, privacy preservation and weather independence. The system performance in terms of accuracy and resource-efficiency is evaluated in the field using comprehensive measurements. Using a machine learning based approach, the resulting success ratio for classifying cars and trucks is above 99%.
Conti, Mauro, Dushku, Edlira, Mancini, Luigi V..  2019.  RADIS: Remote Attestation of Distributed IoT Services. 2019 Sixth International Conference on Software Defined Systems (SDS). :25–32.
Remote attestation is a security technique through which a remote trusted party (i.e., Verifier) checks the trust-worthiness of a potentially untrusted device (i.e., Prover). In the Internet of Things (IoT) systems, the existing remote attestation protocols propose various approaches to detect the modified software and physical tampering attacks. However, in an inter-operable IoT system, in which IoT devices interact autonomously among themselves, an additional problem arises: a compromised IoT service can influence the genuine operation of other invoked service, without changing the software of the latter. In this paper, we propose a protocol for Remote Attestation of Distributed IoT Services (RADIS), which verifies the trust-worthiness of distributed IoT services. Instead of attesting the complete memory content of the entire interoperable IoT devices, RADIS attests only the services involved in performing a certain functionality. RADIS relies on a control-flow attestation technique to detect IoT services that perform an unexpected operation due to their interactions with a malicious remote service. Our experiments show the effectiveness of our protocol in validating the integrity status of a distributed IoT service.
Ji, Yang, Lee, Sangho, Downing, Evan, Wang, Weiren, Fazzini, Mattia, Kim, Taesoo, Orso, Alessandro, Lee, Wenke.  2017.  RAIN: Refinable Attack Investigation with On-Demand Inter-Process Information Flow Tracking. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. :377–390.

As modern attacks become more stealthy and persistent, detecting or preventing them at their early stages becomes virtually impossible. Instead, an attack investigation or provenance system aims to continuously monitor and log interesting system events with minimal overhead. Later, if the system observes any anomalous behavior, it analyzes the log to identify who initiated the attack and which resources were affected by the attack and then assess and recover from any damage incurred. However, because of a fundamental tradeoff between log granularity and system performance, existing systems typically record system-call events without detailed program-level activities (e.g., memory operation) required for accurately reconstructing attack causality or demand that every monitored program be instrumented to provide program-level information. To address this issue, we propose RAIN, a Refinable Attack INvestigation system based on a record-replay technology that records system-call events during runtime and performs instruction-level dynamic information flow tracking (DIFT) during on-demand process replay. Instead of replaying every process with DIFT, RAIN conducts system-call-level reachability analysis to filter out unrelated processes and to minimize the number of processes to be replayed, making inter-process DIFT feasible. Evaluation results show that RAIN effectively prunes out unrelated processes and determines attack causality with negligible false positive rates. In addition, the runtime overhead of RAIN is similar to existing system-call level provenance systems and its analysis overhead is much smaller than full-system DIFT.

Chow, J., Li, X., Mountrouidou, X..  2017.  Raising flags: Detecting covert storage channels using relative entropy. 2017 IEEE International Conference on Intelligence and Security Informatics (ISI). :25–30.

This paper focuses on one type of Covert Storage Channel (CSC) that uses the 6-bit TCP flag header in TCP/IP network packets to transmit secret messages between accomplices. We use relative entropy to characterize the irregularity of network flows in comparison to normal traffic. A normal profile is created by the frequency distribution of TCP flags in regular traffic packets. In detection, the TCP flag frequency distribution of network traffic is computed for each unique IP pair. In order to evaluate the accuracy and efficiency of the proposed method, this study uses real regular traffic data sets as well as CSC messages using coding schemes under assumptions of both clear text, composed by a list of keywords common in Unix systems, and encrypted text. Moreover, smart accomplices may use only those TCP flags that are ever appearing in normal traffic. Then, in detection, the relative entropy can reveal the dissimilarity of a different frequency distribution from this normal profile. We have also used different data processing methods in detection: one method summarizes all the packets for a pair of IP addresses into one flow and the other uses a sliding moving window over such a flow to generate multiple frames of packets. The experimentation results, displayed by Receiver Operating Characteristic (ROC) curves, have shown that the method is promising to differentiate normal and CSC traffic packet streams. Furthermore the delay of raising an alert is analyzed for CSC messages to show its efficiency.

Mohsen, Fadi, Jafaarian, Haadi.  2019.  Raising the Bar Really High: An MTD Approach to Protect Data in Embedded Browsers. 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC). 1:786—794.
The safety of web browsers is essential to the privacy of Internet users and the security of their computing systems. In the last few years, there have been several cyber attacks geared towards compromising surfers' data and systems via exploiting browser-based vulnerabilities. Android and a number of mobile operating systems have been supporting a UI component called WebView, which can be embedded in any mobile application to render the web contents. Yet, this mini-browser component has been found to be vulnerable to various kinds of attacks. For instance, an attacker in her WebView-Embedded app can inject malicious JavaScripts into the WebView to modify the web contents or to steal user's input values. This kind of attack is particularly challenging due to the full control of attackers over the content of the loaded pages. In this paper, we are proposing and testing a server-side moving target defense technique to counter the risk of JavaScript injection attacks on mobile WebViews. The solution entails creating redundant HTML forms, randomizing their attributes and values, and asserting stealthy prompts for the user data. The solution does not dictate any changes to the browser or applications codes, neither it requires key sharing with benign clients. The results of our performance and security analysis suggest that our proposed approach protects the confidentiality and integrity of user input values with minimum overhead.
Hall, Chris, Puder, Doron, Sawin, William F..  2016.  Ramanujan Coverings of Graphs. Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing. :533–541.

Let G be a finite connected graph, and let ρ be the spectral radius of its universal cover. For example, if G is k-regular then ρ=2√k−1. We show that for every r, there is an r-covering (a.k.a. an r-lift) of G where all the new eigenvalues are bounded from above by ρ. It follows that a bipartite Ramanujan graph has a Ramanujan r-covering for every r. This generalizes the r=2 case due to Marcus, Spielman and Srivastava (2013). Every r-covering of G corresponds to a labeling of the edges of G by elements of the symmetric group Sr. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist. In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by Marcus-Spielman-Srivastava, a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from Marcus-Spielman-Srivastava (2015). Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the r-th matching polynomial of G to be the average matching polynomial of all r-coverings of G. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside [−ρ,ρ].

Götzfried, Johannes, Müller, Tilo, Drescher, Gabor, Nürnberger, Stefan, Backes, Michael.  2016.  RamCrypt: Kernel-based Address Space Encryption for User-mode Processes. Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security. :919–924.

We present RamCrypt, a solution that allows unmodified Linux processes to transparently work on encrypted data. RamCrypt can be deployed and enabled on a per-process basis without recompiling user-mode applications. In every enabled process, data is only stored in cleartext for the moment it is processed, and otherwise stays encrypted in RAM. In particular, the required encryption keys do not reside in RAM, but are stored in CPU registers only. Hence, RamCrypt effectively thwarts memory disclosure attacks, which grant unauthorized access to process memory, as well as physical attacks such as cold boot and DMA attacks. In its default configuration, RamCrypt exposes only up to 4 memory pages in cleartext at the same time. For the nginx web server serving encrypted HTTPS pages under heavy load, the necessary TLS secret key is hidden for 97% of its time.

Reyad, O., Karar, M., Hamed, K..  2020.  Random Bit Generator Mechanism Based on Elliptic Curves and Secure Hash Function. 2019 International Conference on Advances in the Emerging Computing Technologies (AECT). :1–6.
Pseudorandom bit generators (PRBG) can be designed to take the advantage of some hard number theoretic problems such as the discrete logarithm problem (DLP). Such type of generators will have good randomness and unpredictability properties as it is so difficult to find an easy solution to the regarding mathematical dilemma. Hash functions in turn play a remarkable role in many cryptographic tasks to achieve various security strengths. In this paper, a pseudorandom bit generator mechanism that is based mainly on the elliptic curve discrete logarithm problem (ECDLP) and hash derivation function is proposed. The cryptographic hash functions are used in consuming applications that require various security strengths. In a good hash function, finding whatever the input that can be mapped to any pre-specified output is considered computationally infeasible. The obtained pseudorandom bits are tested with NIST statistical tests and it also could fulfill the up-to-date standards. Moreover, a 256 × 256 grayscale images are encrypted with the obtained pseudorandom bits following by necessary analysis of the cipher images for security prove.
Li, Z., Li, S..  2017.  Random forest algorithm under differential privacy. 2017 IEEE 17th International Conference on Communication Technology (ICCT). :1901–1905.

Trying to solve the risk of data privacy disclosure in classification process, a Random Forest algorithm under differential privacy named DPRF-gini is proposed in the paper. In the process of building decision tree, the algorithm first disturbed the process of feature selection and attribute partition by using exponential mechanism, and then meet the requirement of differential privacy by adding Laplace noise to the leaf node. Compared with the original algorithm, Empirical results show that protection of data privacy is further enhanced while the accuracy of the algorithm is slightly reduced.

Weedon, M., Tsaptsinos, D., Denholm-Price, J..  2017.  Random forest explorations for URL classification. 2017 International Conference On Cyber Situational Awareness, Data Analytics And Assessment (Cyber SA). :1–4.

Phishing is a major concern on the Internet today and many users are falling victim because of criminal's deceitful tactics. Blacklisting is still the most common defence users have against such phishing websites, but is failing to cope with the increasing number. In recent years, researchers have devised modern ways of detecting such websites using machine learning. One such method is to create machine learnt models of URL features to classify whether URLs are phishing. However, there are varying opinions on what the best approach is for features and algorithms. In this paper, the objective is to evaluate the performance of the Random Forest algorithm using a lexical only dataset. The performance is benchmarked against other machine learning algorithms and additionally against those reported in the literature. Initial results from experiments indicate that the Random Forest algorithm performs the best yielding an 86.9% accuracy.

Sharma, Dilli P., Cho, Jin-Hee, Moore, Terrence J., Nelson, Frederica F., Lim, Hyuk, Kim, Dong Seong.  2019.  Random Host and Service Multiplexing for Moving Target Defense in Software-Defined Networks. ICC 2019 - 2019 IEEE International Conference on Communications (ICC). :1—6.

Moving target defense (MTD) is a proactive defense mechanism of changing the attack surface to increase an attacker's confusion and/or uncertainty, which invalidates its intelligence gained through reconnaissance and/or network scanning attacks. In this work, we propose software-defined networking (SDN)-based MTD technique using the shuffling of IP addresses and port numbers aiming to obfuscate both network and transport layers' real identities of the host and the service for defending against the network reconnaissance and scanning attacks. We call our proposed MTD technique Random Host and Service Multiplexing, namely RHSM. RHSM allows each host to use random, multiple virtual IP addresses to be dynamically and periodically shuffled. In addition, it uses short-lived, multiple virtual port numbers for an active service running on the host. Our proposed RHSM is novel in that we employ multiplexing (or de-multiplexing) to dynamically change and remap from all the virtual IPs of the host to the real IP or the virtual ports of the services to the real port, respectively. Via extensive simulation experiments, we prove how effectively and efficiently RHSM outperforms a baseline counterpart (i.e., a static network without RHSM) in terms of the attack success probability and defense cost.

Zadeh, B.Q., Handschuh, S..  2014.  Random Manhattan Indexing. Database and Expert Systems Applications (DEXA), 2014 25th International Workshop on. :203-208.

Vector space models (VSMs) are mathematically well-defined frameworks that have been widely used in text processing. In these models, high-dimensional, often sparse vectors represent text units. In an application, the similarity of vectors -- and hence the text units that they represent -- is computed by a distance formula. The high dimensionality of vectors, however, is a barrier to the performance of methods that employ VSMs. Consequently, a dimensionality reduction technique is employed to alleviate this problem. This paper introduces a new method, called Random Manhattan Indexing (RMI), for the construction of L1 normed VSMs at reduced dimensionality. RMI combines the construction of a VSM and dimension reduction into an incremental, and thus scalable, procedure. In order to attain its goal, RMI employs the sparse Cauchy random projections.

K. Sathya, J. Premalatha, V. Rajasekar.  2015.  "Random number generation based on sensor with decimation method". 2015 IEEE Workshop on Computational Intelligence: Theories, Applications and Future Directions (WCI). :1-5.

Strength of security and privacy of any cryptographic mechanisms that use random numbers require that the random numbers generated have two important properties namely 1. Uniform distribution and 2. Independence. With the growth of Internet many devices are connected to Internet that host sensors. One idea proposed is to use sensor data as seed for Random Number Generator (RNG) since sensors measure the physical phenomena that exhibit randomness over time. The random numbers generated from sensor data can be used for cryptographic algorithms in Internet activities. These sensor data also pose weaknesses where sensors may be under adversarial control that may lead to generating expected random sequence which breaks the security and privacy. This paper proposes a wash-rinse-spin approach to process the raw sensor data that increases randomness in the seed value. The generated sequences from two sensors are combined by Decimation method to improve unpredictability. This makes the sensor data to be more secure in generating random numbers preventing attackers from knowing the random sequence through adversarial control.

Boyacı, O., Tantuğ, A. C..  2017.  A random number generation method based on discrete time chaotic maps. 2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS). :1212–1215.

In this paper a random number generation method based on a piecewise linear one dimensional (PL1D) discrete time chaotic maps is proposed for applications in cryptography and steganography. Appropriate parameters are determined by examining the distribution of underlying chaotic signal and random number generator (RNG) is numerically verified by four fundamental statistical test of FIPS 140-2. Proposed design is practically realized on the field programmable analog and digital arrays (FPAA-FPGA). Finally it is experimentally verified that the presented RNG fulfills the NIST 800-22 randomness test without post processing.

Erbay, C., Ergïn, S..  2018.  Random Number Generator Based on Hydrogen Gas Sensor for Security Applications. 2018 IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS). :709–712.
Cryptographic applications need high-quality random number generator (RNG) for strong security and privacy measures. This paper presents RNG based on a hydrogen gas sensor that is fabricated by using microfabrication techniques. The proposed approach extracts the thermal noise information as an entropy source from the gas sensor that is non-deterministic during its operation and using hash function SHA-256 as post processing. This non-deterministic noise is then processed to acquire a random number set fulfilling the NIST 800-22 statistical randomness test suite and it demonstrates that a gas sensor based RNG can provide high-quality random numbers. Secure data transfer is possible by having this method directly without any other hardware where hydrogen gas sensor needs to be used such as petrochemical field, fuel cells, and nuclear reactors.
Ergün, S., Tanrıseven, S..  2020.  Random Number Generator Based on Skew-tent Map and Chaotic Sampling. 2020 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS). :224–227.
In this paper a novel random number generator is introduced and it is based on the Skew-tent discrete-time chaotic map. The RNG presented in this paper is made using the discrete-time chaotic map and chaotic sampling of regular waveform method together to increase the throughput and statistical quality of the output sequence. An explanation of the arithmetic model for the proposed design is given in this paper with an algebra confirmation for the generated bit stream that shows how it passes the primary four tests of the FIPS-140-2 test suit successfully. Finally the bit stream resulting from the hardware implementation of the circuit in a similar method has been confirmed to pass all NIST-800-22 test with no post processing. A presentation of the experimentally obtained results is given therefor proving the the circuit’s usefulness. The proposed RNG can be built with the integrated circuit.
Ming, Z., Zheng-jiang, W., Liu, H..  2017.  Random Projection Data Perturbation Based Privacy Protection in WSNs. 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). :493–498.

Wireless sensor networks are responsible for sensing, gathering and processing the information of the objects in the network coverage area. Basic data fusion technology generally does not provide data privacy protection mechanism, and the privacy protection mechanism in health care, military reconnaissance, smart home and other areas of the application is usually indispensable. In this paper, we consider the privacy, confidentiality, and the accuracy of fusion results, and propose a data fusion algorithm for privacy preserving. This algorithm relies on the characteristics of data fusion, and uses the method of pre-distribution random number in the node to get the privacy protection requirements of the original data. Theoretical analysis shows that the malicious attacker attempts to steal the difficulty of node privacy in PPND algorithm. At the same time in the TOSSIM simulation results also show that, compared with TAG, SMART algorithm, PPND algorithm in the data traffic, the convergence accuracy of the good performance.

Choi, Jungyong, Shin, WoonSeob, Kim, Jonghyun, Kim, Ki-Hyung.  2020.  Random Seed Generation For IoT Key Generation and Key Management System Using Blockchain. 2020 International Conference on Information Networking (ICOIN). :663–665.
Recently, the Internet of Things (IoT) is growing rapidly. IoT sensors are attached to various devices, and information is detected, collected and utilized through various wired and wireless communication environments. As the IoT is used in various places, IoT devices face a variety of malicious attacks such as MITM and reverse engineering. To prevent these, encryption is required for device-to-device communication, and keys required for encryption must be properly managed. We propose a scheme to generate seed needed for key generation and a scheme to manage the public key using blockchain.
Anupadma, S., Dharshini, B. S., Roshini, S., K, J. Singh.  2020.  Random selective block encryption technique for image cryptography using chaotic cryptography. 2020 International Conference on Emerging Trends in Information Technology and Engineering (ic-ETITE). :1–5.
Dynamic random growth technique and a hybrid chaotic map which is proposed in this paper are used to perform block-based image encryption. The plaintext attack can easily crack the cat map, as it is periodic, and therefore cat map securely used in which it can eliminate the cyclical occurrence and withstand the plaintext attack's effect. The diffusion process calculates the intermediate parameters according to the image block. For the generation of the random data stream in the chaotic map, we use an intermediate parameter as an initial parameter. In this way, the generated data stream depends on the plain text image that can withstand the attack on plain text. The experimental results of this process prove that the proposed dynamic random growth technique and a hybrid chaotic map for image encryption is a secured one in which it can be used in secured image transmission systems.
Taggu, Amar, Marchang, Ningrinla.  2019.  Random-Byzantine Attack Mitigation in Cognitive Radio Networks using a Multi-Hidden Markov Model System. 2019 International Conference on Electrical and Computing Technologies and Applications (ICECTA). :1—5.
Cognitive Radio Networks (CRN) are opportunistic networks which aim to harness the white space in the television frequency spectrum, on a need-to-need basis, without interfering the incumbent, called the Primary User (PU). Cognitive radios (CR) that sense the spectrum periodically for sensing the PU activity, are called Secondary Users (SU). CRNs are susceptible to two major attacks, Byzantine attacks and Primary User Emulation Attack (PUEA). Both the attacks are capable of rendering a CRN useless, by either interfering with the PU itself or capturing the entire channel for themselves. Byzantine attacks detection and mitigation is an important security issue in CRN. Hence, the current work proposes using a multi-Hidden Markov Model system with an aim to detect different types of random-Byzantine attacks. Simulation results show good detection rate across all the attacks.
Zhang, Kai, Liu, Chuanren, Zhang, Jie, Xiong, Hui, Xing, Eric, Ye, Jieping.  2017.  Randomization or Condensation?: Linear-Cost Matrix Sketching Via Cascaded Compression Sampling Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. :615–623.
Matrix sketching is aimed at finding compact representations of a matrix while simultaneously preserving most of its properties, which is a fundamental building block in modern scientific computing. Randomized algorithms represent state-of-the-art and have attracted huge interest from the fields of machine learning, data mining, and theoretic computer science. However, it still requires the use of the entire input matrix in producing desired factorizations, which can be a major computational and memory bottleneck in truly large problems. In this paper, we uncover an interesting theoretic connection between matrix low-rank decomposition and lossy signal compression, based on which a cascaded compression sampling framework is devised to approximate an m-by-n matrix in only O(m+n) time and space. Indeed, the proposed method accesses only a small number of matrix rows and columns, which significantly improves the memory footprint. Meanwhile, by sequentially teaming two rounds of approximation procedures and upgrading the sampling strategy from a uniform probability to more sophisticated, encoding-orientated sampling, significant algorithmic boosting is achieved to uncover more granular structures in the data. Empirical results on a wide spectrum of real-world, large-scale matrices show that by taking only linear time and space, the accuracy of our method rivals those state-of-the-art randomized algorithms consuming a quadratic, O(mn), amount of resources.
Liu, Mingmou, Pan, Xiaoyin, Yin, Yitong.  2016.  Randomized Approximate Nearest Neighbor Search with Limited Adaptivity. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. :23–33.

We study the problem of approximate nearest neighbor search in \$d\$-dimensional Hamming space \0,1\d. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe model with limited adaptivity, where the algorithm makes k rounds of parallel accesses to the data structure for a given k. For any k ≥ 1, we give a simple randomized algorithm solving the approximate nearest neighbor search using k rounds of parallel memory accesses, with O(k(log d)1/k) accesses in total. We also give a more sophisticated randomized algorithm using O(k+(1/k log d)O(1/k)) memory accesses in k rounds for large enough k. Both algorithms use data structures of size polynomial in n, the number of points in the database. We prove an Ω(1/k(log d)1/k) lower bound for the total number of memory accesses required by any randomized algorithm solving the approximate nearest neighbor search within k ≤ (log log d)/(2 log log log d) rounds of parallel memory accesses on any data structures of polynomial size. This lower bound shows that our first algorithm is asymptotically optimal for any constant round k. And our second algorithm approaches the asymptotically optimal tradeoff between rounds and memory accesses, in a sense that the lower bound of memory accesses for any k1 rounds can be matched by the algorithm within k2=O(k1) rounds. In the extreme, for some large enough k=Θ((log log d)/(log log log d)), our second algorithm matches the Θ((log log d)/(log log log d)) tight bound for fully adaptive algorithms for approximate nearest neighbor search due to Chakrabarti and Regev.